package Sort;

import java.util.Arrays;

public class leet_912 {
    public static void main(String[] args) {
        Solution_912 p = new Solution_912();
        int[] nums = new int[]{5,1,1,2,0,0};

        int[] value = p.sortArray(nums);
        System.out.println(Arrays.toString(value));
    }
}


class Solution_912 {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    /**
     * 快速排序
     * @param nums  排序数组
     * @param left  左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right) {
        // 递归函数最重要的需要定义结束条件
        if(left > right){
            // 这个位置只有一个元素不需要排序
            return;
        }


        // 定义中间值
        int medium = nums[left];
        int i=left;
        int j=right;

        // 当i和j相遇时代表已经按照medium 排好顺序了
        while(i!=j){
            // 一定要优先移动右指针
            // 找到小于medium 值
            while(nums[j]>=medium && i<j){
                j--;
            }

            // 移动左指针
            // 找到大于medium的值
            while(nums[i]<=medium && i<j){
                i++;
            }

            // 相遇代表2边存在值需要交换
            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 当拍完顺序后代表medium 左边都是小于的 右边都是大于的
        // 将medium放到对应的位置i上
        nums[left] = nums[i];
        nums[i] = medium;

        // 由于i本身已经排好顺序了 需要排序 i的左边与右边
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
    }

}
